home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / game / board / Crafty-15.19.lha / crafty-15.19 / src / book.c < prev    next >
C/C++ Source or Header  |  1998-09-16  |  50KB  |  1,252 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <string.h>
  5. #include "chess.h"
  6. #include "data.h"
  7. #if defined(UNIX)
  8. #  include <unistd.h>
  9. #endif
  10.  
  11. /* last modified 08/26/98 */
  12. /*
  13. ********************************************************************************
  14. *                                                                              *
  15. *   Book() is used to determine if the current position is in the book data-   *
  16. *   base.  it simply takes the set of moves produced by root_moves() and then  *
  17. *   tries each position's hash key to see if it can be found in the data-      *
  18. *   base.  if so, such a move represents a "book move."  the set of flags is   *
  19. *   used to decide on a sub-set of moves to be used as the "book move pool"    *
  20. *   from which a move is chosen randomly.                                      *
  21. *                                                                              *
  22. *   the format of a book position is as follows:                               *
  23. *                                                                              *
  24. *   64 bits:  hash key for this position.                                      *
  25. *                                                                              *
  26. *    8 bits:  flag bits defined as  follows:                                   *
  27. *                                                                              *
  28. *      0000 0001  ?? flagged move                (0001) (0x01)                 *
  29. *      0000 0010   ? flagged move                (0002) (0x02)                 *
  30. *      0000 0100   = flagged move                (0004) (0x04)                 *
  31. *      0000 1000   ! flagged move                (0010) (0x08)                 *
  32. *      0001 0000  !! flagged move                (0020) (0x10)                 *
  33. *      0010 0000     black won at least 1 game   (0040) (0x20)                 *
  34. *      0100 0000     at least one game was drawn (0100) (0x40)                 *
  35. *      1000 0000     white won at least 1 game   (0200) (0x80)                 *
  36. *                                                                              *
  37. *   24 bits:  number of games this move was played.                            *
  38. *                                                                              *
  39. *   32 bits:  learned value (floating point).                                  *
  40. *                                                                              *
  41. *     (note:  counts are normalized to a max of 255.                           *
  42. *                                                                              *
  43. ********************************************************************************
  44. */
  45. #define BAD_MOVE  002
  46. #define GOOD_MOVE 010
  47.  
  48. int Book(TREE *tree, int wtm, int root_list_done) {
  49.   static int book_moves[200];
  50.   static BOOK_POSITION start_moves[200];
  51.   static int selected[200];
  52.   static int selected_order_played[200], selected_value[200];
  53.   static int selected_status[200], selected_percent[200], book_development[200];
  54.   static int bs_played[200], bs_percent[200];
  55.   static int book_status[200], evaluations[200], bs_learn[200];
  56.   static float bs_value[200], total_value;
  57.   int m1_status, forced=0, total_percent;
  58.   float tempr;
  59.   int done, i, j, last_move, temp, which, minlv=999999, maxlv=-999999;
  60.   int maxp=-999999, minev=999999, maxev=-999999;
  61.   int *mv, mp, value, np;
  62.   int cluster, scluster, test;
  63.   BITBOARD temp_hash_key, common;
  64.   int key, nmoves, num_selected, st;
  65.   int percent_played, total_played, total_moves, smoves;
  66.   int distribution;
  67.   int initial_development;
  68.   char *whisper_p;
  69. /*
  70.  ----------------------------------------------------------
  71. |                                                          |
  72. |   if we have been out of book for several moves, return  |
  73. |   and start the normal tree search.                      |
  74. |                                                          |
  75.  ----------------------------------------------------------
  76. */
  77.   if (moves_out_of_book > 3) return(0);
  78. /*
  79.  ----------------------------------------------------------
  80. |                                                          |
  81. |   position is known, read the start book file and save   |
  82. |   each move found.  these will be used later to augment  |
  83. |   the flags in the normal book to offer better control.  |
  84. |                                                          |
  85.  ----------------------------------------------------------
  86. */
  87.   if (!root_list_done) RootMoveList(wtm);
  88.   test=HashKey>>49;
  89.   smoves=0;
  90.   if (books_file) {
  91.     fseek(books_file,test*sizeof(int),SEEK_SET);
  92.     fread(&key,sizeof(int),1,books_file);
  93.     if (key > 0) {
  94.       fseek(books_file,key,SEEK_SET);
  95.       fread(&scluster,sizeof(int),1,books_file);
  96.       fread(books_buffer,sizeof(BOOK_POSITION),scluster,books_file);
  97.       for (mv=tree->last[0];mv<tree->last[1];mv++) {
  98.         common=And(HashKey,mask_16);
  99.         MakeMove(tree,1,*mv,wtm);
  100.         if (RepetitionCheck(tree,2,ChangeSide(wtm))) {
  101.           UnMakeMove(tree,1,*mv,wtm);
  102.           return(0);
  103.         }
  104.         temp_hash_key=Xor(HashKey,wtm_random[wtm]);
  105.         temp_hash_key=Or(And(temp_hash_key,Compl(mask_16)),common);
  106.         for (i=0;i<scluster;i++)
  107.           if (!Xor(temp_hash_key,books_buffer[i].position)) {
  108.             start_moves[smoves++]=books_buffer[i];
  109.             break;
  110.           }
  111.         UnMakeMove(tree,1,*mv,wtm);
  112.       }
  113.     }
  114.   }
  115. /*
  116.  ----------------------------------------------------------
  117. |                                                          |
  118. |   position is known, read in the appropriate cluster.    |
  119. |   note that this cluster will have all possible book     |
  120. |   moves from current position in it (as well as others   |
  121. |   of course.)                                            |
  122. |                                                          |
  123.  ----------------------------------------------------------
  124. */
  125.   test=HashKey>>49;
  126.   if (book_file) {
  127.     fseek(book_file,test*sizeof(int),SEEK_SET);
  128.     fread(&key,sizeof(int),1,book_file);
  129.     if (key > 0) {
  130.       fseek(book_file,key,SEEK_SET);
  131.       fread(&cluster,sizeof(int),1,book_file);
  132.       fread(book_buffer,sizeof(BOOK_POSITION),cluster,book_file);
  133.     }
  134.     else cluster=0;
  135.     if (!cluster) return(0);
  136. /*
  137.  ----------------------------------------------------------
  138. |                                                          |
  139. |   now add any moves from books.bin to the end of the     |
  140. |   cluster so that they will be played even if not in the |
  141. |   regular database of moves.                             |
  142. |                                                          |
  143.  ----------------------------------------------------------
  144. */
  145.     for (i=0;i<smoves;i++) {
  146.       for (j=0;j<cluster;j++) 
  147.         if (!Xor(book_buffer[j].position,start_moves[i].position)) break;
  148.       if (j >= cluster) {
  149.         book_buffer[cluster]=start_moves[i];
  150.         book_buffer[cluster].status_played=
  151.           book_buffer[cluster].status_played&037700000000;
  152.         cluster++;
  153.       }
  154.     }
  155. /*
  156.  ----------------------------------------------------------
  157. |                                                          |
  158. |   first cycle through the root move list, make each      |
  159. |   move, and see if the resulting hash key is in the book |
  160. |   database.                                              |
  161. |                                                          |
  162.  ----------------------------------------------------------
  163. */
  164.     initial_development=(wtm) ? EvaluateDevelopment(tree,1) : 
  165.                                -EvaluateDevelopment(tree,1);
  166.     total_moves=0;
  167.     nmoves=0;
  168.     for (mv=tree->last[0];mv<tree->last[1];mv++) {
  169.       common=And(HashKey,mask_16);
  170.       MakeMove(tree,1,*mv,wtm);
  171.       if (RepetitionCheck(tree,2,ChangeSide(wtm))) {
  172.         UnMakeMove(tree,1,*mv,wtm);
  173.         return(0);
  174.       }
  175.       temp_hash_key=Xor(HashKey,wtm_random[wtm]);
  176.       temp_hash_key=Or(And(temp_hash_key,Compl(mask_16)),common);
  177.       for (i=0;i<cluster;i++) {
  178.         if (!Xor(temp_hash_key,book_buffer[i].position)) {
  179.           book_status[nmoves]=book_buffer[i].status_played>>24;
  180.           bs_played[nmoves]=book_buffer[i].status_playe